/*
 * Copyright (C), 2015-2018
 * FileName: Solution169
 * Author:   zhao
 * Date:     2018/9/22 16:48
 * Description: 169. 求众数
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredtwo;

import java.util.Collections;
import java.util.HashMap;

/**
 * 〈一句话功能简述〉<br>
 * 〈169. 求众数〉
 *
 * @author zhao
 * @date 2018/9/22 16:48
 * @since 1.0.1
 */
public class Solution169 {

  /**************************************
   * 题目
   给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

   你可以假设数组是非空的，并且给定的数组总是存在众数。

   示例 1:

   输入: [3,2,3]
   输出: 3
   示例 2:

   输入: [2,2,1,1,1,2,2]
   输出: 2
   **************************************/

  /**************************************
   *
   * 想法：
   *    一、暴力法 时间空间复杂度都是O(n)
   *      搞一个map，key是数组中的元素，值是次数，这时候事件
   *    二、排序取中值
   *      对数组进行排序，在中间的那个，肯定是结果
   *    三、分治法
   *       https://blog.csdn.net/qq_38595487/article/details/79435799
   *      分治法是将整个问题化简为一个一个的小问题去解，
   *      将数组分成简单的几部分，
   *      比如讲一组数分为两部分，第一部分的众数如果等于第二部分的众数，则这个数就是上一层那一组的众数，
   *      如果第一部分不等于第二部分，则遍历这一组数，记录这两个数的出现频率，返回为频率最大的，
   *      如果频率相同，返回谁都无所谓，因为在这里众数x肯定存在的，
   *      那么肯定会有至少两个x相连，如果不相连的话，
   *      那最后一个数字肯定是众数x。（例如：1 2 1 2 1 2 1，12112）。时间复杂度为o(n)。
   *
   * ---------------------
   *
   * 我的做法
   *      超过  %的测试案例
   *
   * 代码执行过程：
   *
   * 总结：
   *
   * ***********************************/
  public int majorityElement(int[] nums) {
    // 排序法
    // return majorityElementBySort(nums);
    return find(nums, 0, nums.length - 1);
  }

  public int find(int[] nums, int begin, int end) {
    if (begin == end) {
      return nums[begin];
    }

    int mid = (begin + end) / 2;
    int left = find(nums, begin, mid);
    int right = find(nums, mid + 1, end);

    if (left == right) {
      return left;
    }

    int countLeft = 0;
    int countRight = 0;
    for (int i = begin; i <= end; i++) {
      if (nums[i] == left) {
        countLeft++;
      } else if (nums[i] == right) {
        countRight++;
      }
    }
    return countLeft > countRight ? left : right;
  }

  public int majorityElementBySort(int[] nums) {

    // 排序方法
    // 冒泡排序，这里排序到一半，到了中间位置就叫停了
    for (int i = 1; i < nums.length / 2 + 2; i++) {
      for (int j = 0; j < nums.length - i; j++) {
        if (nums[j] > nums[j + 1]) {
          int temp = nums[j];
          nums[j] = nums[j + 1];
          nums[j + 1] = temp;
        }
      }
    }

    return nums[nums.length / 2];
  }

  /**************************************
   * 比我好的答案 better
   * ***********************************/
  public void better() {
  }

}
